Purpose: Warm-up exercise to get you back into Java programming.
Marking: All questions are binary marked.
To hand-in: Print out the code and documentation you have written, and a
coursework coversheet. Read and fill in the cover sheet, sign it and attach it
to the print-out. Submit to the departmental office. Work can also be marked
during a lab session but should still be submitted to the departmental office.
Work should also be submitted electronically (instructions will be sent at the
deadline).
All printing should be done on the line printer (a4lp) - don't use
up your laser printer quota!
NOTE: You must keep all marked work as it forms a record of your progress. At the end of the course you are required to re-submit all work.
1. This exercise is about implementing a linked-list class. The Java language features needed to implement a list class were all covered in 1B11, so it would be a good idea to revise them first. An introduction to linked-lists was also included as part of 1b11 and there is detailed information in the text book (Developing Java Software). The 1b11 slides on linked-lists are still on the web at: http://www.cs.ucl.ac.uk/staff/G.Roberts/2000/1b11/slides20.pdf.
A typical list class stores a chain of list elements each holding a reference to the next element in the chain and a reference to a data object. Write a single-link list class implementing the LinkedList interface below (single-link means that the list element has a single reference to the next element in the chain).
public interface LinkedList
{
public Object getHead() ; // Return object at head of list or null if
// list is empty.
public LinkedList getTail() ; // Return a copy of the tail of the list
// (all elements except the first).
public void addHead(Object o) ; // Add object to head of list.
public void addTail(Object o) ; // Add object at end of list.
public LinkedList append(LinkedList l) ;
// Return a new list consisting of the
// a copy of the current list with a copy
// of the argument list l appended.
public boolean isEmpty() ; // Return true if no objects in the list.
public LinkedListIterator iterator() ;
// Return an iterator object for the list.
}
An iterator class implementing the LinkedListIterator interface will also be
needed.
public interface LinkedListIterator
{
public boolean hasNext() ; // Return true if there is another object in the list.
public Object next() ; // Move to next object in list and return its reference.
}
The 1b11 slides on lists outline an implementation of this kind of list. Make sure that your list element and iterator classes are nested inside the list class.
The list iterator provides a mechanism for accessing the elements in the list in sequence. Remember how the list iterator works:
LinkedList myList = new LinkedListImpl() ; // Create an empty list.
...
// Fill up list
...
LinkedListIterator myIterator = myList.iterator() ; // Get an iterator
while (myIterator.hasNext())
{
... = (someType) myIterator.next() ; // Get the element and cast its type
// Do something with the element
...
}
2. To verify that your linked list class works we will use the London Underground route finding problem (an old-favourite you may have done before but it is really good for testing lists! Plus CS students must solve this problem in multiple different ways - its the law or something).
Write a program that will find a route between any two stations on the London Underground network. Given a start and end station the program should list each station and change of line that forms the route.
Here is a suggested implementation strategy (feel free to invent your own providing it uses your list class and iterator).
i) Create a class Station that holds a list of all connecting lines at that station.
ii) Create a class Line that holds a list of stations on the line.
iii) Create a class Network that holds a list of all the lines.
(Note, the underground will effectively be represented by a list of lists of lists.)
iv) Write an initalisation class to read in the line and station data from a file to initialise your program. Store the data in a text file that has the following sort of layout:
Line: Victoria Brixton Stockwell Vauxhall Pimlico Victoria etc.
A new line is marked by the keyword Line: followed by the line name. Every following text line then holds the name of a station. Of course(!), you will have to extend this format to deal with the fact that many lines have branches (the line splits and goes to several destinations). Further, you need to deal with the Circle line and the West End and City branches of the Northern line. For this exercise you can take the simple approach by splitting the lines into distinct sections.
Many stations are on more than one line and a given station should be
represented by a single object only. To fully initialise a station object you
need to know the complete list of lines it is on. As you read the data file, a
station object will be created before you know all the lines it is on. One way
of dealing with this is as follows:
a) Keep a list of all stations read so
far.
b) Read a station name and check the all stations list to see if the
station object already exists. If it does then add the existing object to the
current line list. Add the line to the station’s list of connecting lines.
c) If a station is new, create a new object and add it to both the current
line and the all stations list.
v) As part of your Network class write methods to search your data structure of lists and objects to find a route. There are lots of algorithms that can be used. The simplest is a depth first recursive search.
To avoid everybody typing in the names of all the stations on the underground there is a list on the web. See the 2b11 web page. Also the official tube website is at: http://www.thetube.com/.
Note: Your answers to these questions will be needed for later exercises.